// ------------------------------------------------------------------------------------------------
// ---- Livro Algoritmos (de Cormen, Leiserson, Rivest, Stein) ------------------------------------
// ---- Cortes de Hastes (Capítulo 15.1) ----------------------------------------------------------
// ------------------------------------------------------------------------------------------------
#include <iostream>
#include <vector>
using namespace std;


// -------------------------------------------------------------
// ---- ALGORITMO HASTES ---------------------------------------
// -------------------------------------------------------------
int Hastes(vector<int>& p, int N, vector<int>& q, vector<int>& R) {
    q[0] = 0;
    for (int j=1; j<=N; j++) {
        q[j] = -INT_MAX; // -infinito
        for (int i=1; i<=j; i++) {
            if (q[j] < p[i]+q[j-i]) {
                R[j] = i;
                q[j] = p[i]+q[j-i];
            }
        }
    }
    return q[N];
}

// -------------------------------------------------------------
// --- MAIN ----------------------------------------------------
// -------------------------------------------------------------
int main() {
    // Valor da haste para cada tamanho:  p[0]  = 0
    //                 0, 1, 2, 3, 4, 5,  6,  7,  8,  9
    //vector<int> p = {0, 1, 5, 8, 9, 10, 17, 17, 20, 24};
    vector  <int> p = {0, 1, 5, 7, 9, 11, 14, 16, 19, 21};
    int N = p.size()-1;

    vector<int> q (N+1, 0);
    vector<int> R (N+1, 0);
    int opt = Hastes(p, N, q, R);

    int k;
    for (k=1; k<=N; k++) {
        cout << "Lucro maximo para haste de tamanho " << k << " = " << q[k] << "\n";
    }

    cout << "\n\n";
    cout << "Lucro maximo para a haste inteira = " << opt << "\n";
    cout << "Tamanhos dos cortes a serem feitos:\n";

    k = N;
    while (k > 0) {
        cout << R[k] << " ";
        k = k - R[k];
    }

    cout << "\n\n\n\n\n\n";
    //for (k=0; k<=N; k++) cout << R[k] << " ";

    k = N;
    while (k > 0) {
        cout << R[k] << " ";
        k = k - R[k];
        if (k>0) cout << "+ ";
    }
    cout << "= " << N;
    cout << "\n\n\n\n\n\n";
    return 0;
}